/**
 * 顺序表异常类
 */
class SeqException :public exception
{
public:
	SeqException() :exception("未知错误！\n") {}

	class IndexOutOfRange : public exception {
	public:
		const char* what()const throw()
		{
			return "下标越界！\n";
		}
	};
};

/**
 * 顺序表类
 */
template <typename Type>
class SeqList
{
public:
	SeqList();
	SeqList(int capacity);
	SeqList(Type a[], int start, int end);
	SeqList(const SeqList& sl);
	int length();
	bool isEmpty();
	void resize(int size);
	Type get(int index) throw (SeqException::IndexOutOfRange);
	int firstIndexOf(Type value);
	int lastIndexOf(Type value);
	void add(Type value);
	void insert(int index, Type value) throw (SeqException::IndexOutOfRange);
	Type remove(int index) throw (SeqException::IndexOutOfRange);
	void clear();
	void printList();
	~SeqList();
private:
	Type* data;
	int len;
};

//默认构造
template <typename Type>
SeqList<Type>::SeqList()
{
	len = 0;
	data = new Type[10];
}

//初始化构造
template <typename Type>
SeqList<Type>::SeqList(int capacity)
{
	len = 0;
	data = new Type[capacity];
}

//利用数组构造
template <typename Type>
SeqList<Type>::SeqList(Type a[], int start, int end)
{
	len = end - start + 1;
	data = new Type[len];
	for (int i = start, j = 0; i <= end; i++, j++)
	{
		data[j] = a[i];
	}
}

//拷贝构造
template <typename Type>
SeqList<Type>::SeqList(const SeqList& sl)
{
	len = sl.len;
	data = new Type[len];
	for (int i = 0; i < len; i++)
	{
		data[i] = sl.data[i];
	}
}

//获取顺序表长度
template <typename Type>
int SeqList<Type>::length()
{
	return len;
}

//判断顺序表是否为空
template <typename Type>
bool SeqList<Type>::isEmpty()
{
	return len == 0;
}

//重设顺序表容量
template <typename Type>
void SeqList<Type>::resize(int capacity)
{
	Type* tmp = new Type[capacity];
	for (int i = 0; i < len; i++)
	{
		tmp[i] = data[i];
	}
	delete[] data;
	data = tmp;
}

//通过位置查找元素
template <typename Type>
Type SeqList<Type>::get(int index) throw (SeqException::IndexOutOfRange)
{
	if (index < 0 || index > length - 1)
	{
		//抛出位置越界异常
		throw SeqException::IndexOutOfRange();
	}

	return data[index];
}

//查找元素第一次出现在顺序表中的位置
template <typename Type>
int SeqList<Type>::firstIndexOf(Type value)
{
	for (int i = 0; i < len; i++)
	{
		if (data[i] == value)
		{
			return i;
		}
	}
	return -1;
}

//查找元素最后一次出现在顺序表中的位置
template <typename Type>
int SeqList<Type>::lastIndexOf(Type value)
{
	for (int i = len - 1; i >= 0; i--)
	{
		if (data[i] == value)
		{
			return i;
		}
	}
	return -1;
}

//尾插元素
template <typename Type>
void SeqList<Type>::add(Type value)
{
	insert(len, value);
	// 容量不够时，重设顺序表容量为当前容量的2倍
	// if (index == len)
	// {
	// 	resize(len * 2);
	// }
	// data[len++] = value;
}

//在指定位置插入元素
template <typename Type>
void SeqList<Type>::insert(int index, Type value) throw (SeqException::IndexOutOfRange)
{
	if (index < 0 || index > len)
	{
		//抛出位置越界异常
		throw SeqException::IndexOutOfRange();
	}

	//容量不够时，重设顺序表容量为当前容量的2倍
	if (index == len)
	{
		resize(len * 2);
	}

	for (int i = len; i > index; i--)
	{
		data[i] = data[i - 1];
	}
	data[index] = value;
	len++;
}

//删除并返回指定位置元素
template <typename Type>
Type SeqList<Type>::remove(int index) throw (SeqException::IndexOutOfRange)
{
	if (index < 0 || index > len - 1)
	{
		//抛出位置越界异常
		throw SeqException::IndexOutOfRange();
	}

	Type  value = data[index];
	for (int i = index; i < len; i++)
	{
		data[i] = data[i + 1];
	}
	len--;

	//当长度小于等于当前容量的1/4时，重设顺序表容量为当前容量的1/2
	if (len <= sizeof(data) / sizeof(data[0]) / 4)
	{
		resize(sizeof(data) / sizeof(data[0]) / 2);
	}
	return value;
}

//清空顺序表
template <typename Type>
void SeqList<Type>::clear()
{
	len = 0;
	resize(10);
}

//打印顺序表
template <typename Type>
void SeqList<Type>::printList()
{
	for (int i = 0; i < len; i++)
	{
		cout << "第" << i + 1 << "个元素的值为：" << data[i] << endl;
	}
}

//析构函数
template <typename Type>
SeqList<Type>::~SeqList()
{
	delete[] data;
}